<?php 
  /**
   * @author claudiugh
   */
require_once('PT_Arc.class.php');
require_once('PT_Line.class.php');
require_once('PT_Network.class.php');
require_once('PT_MapNode.class.php');
require_once('PT_Grid.class.php');
require_once('util.class.php');

class PT_GraphNode
{
  var $net_id;
  var $line_id;
  var $name;
  
  /**
   * @param $net_id int index of the network within the graph 
   * @param $line_id int index of the line within the network
   * @param $name string 
   */
  function PT_GraphNode($net_id, $line_id, $name)
  {
    $this->net_id = $net_id;
    $this->line_id = $line_id;
    $this->name = $name;
  }
}


class PT_GraphEdge
{
  var $to;
  var $w;
  function PT_GraphEdge($to, $w)
  {
    $this->to = $to;
    $this->w = $w;
  }
}

class PT_Graph
{
  var $vertex;
  var $networks;
  var $adjlist;
  var $grid;

  /**
   * Constructor 
   */

  function PT_Graph()
  {
    $this->vertex = array();
    $this->networks = array(new PT_Network('WALK'));
    $this->networks[0]->add_line(new PT_Line('WALK'));
    $this->adjlist = array();
    $this->grid = new PT_Grid(); 
  }

  function add_edge($from_id, $to_id, $w)
  {
    array_push($this->adjlist[$from_id], new PT_GraphEdge($to_id, $w));
  }

  function add_node($net_id, $line_id, $name)
  {
    array_push($this->vertex, new PT_GraphNode($net_id, $line_id, $name));
    $node_id = count($this->vertex) - 1;
    $this->adjlist[$node_id] = array(); 
    return $node_id;
  }
		    
  /**
   * @param $network PT_Network object 
   */
  function add_network(PT_Network $network)
  {
    array_push($this->networks, $network);
    $net_id = count($this->networks) - 1;
    // for each line 
    for ($line_id = 0; $line_id < count($network->lines); $line_id++)
      {
	$ids_hash = array();
	// for each station 
	foreach ($network->lines[$line_id]->stations_hash as $name => $pos)
	  {
	    $node_id = $this->add_node($net_id, $line_id, $name);
	    $this->grid->add_map_point($node_id, $pos);
	    $ids_hash[$name] = $node_id; 
	  }

	// add the adjlist in the internal data adj list
	foreach ($network->lines[$line_id]->arcs as $arc)
	  {
	    $this->add_edge($ids_hash[$arc->from], $ids_hash[$arc->to], $arc->w);
	    if ($arc->dir == PT_BIDIR)
	      $this->add_edge($ids_hash[$arc->to], $ids_hash[$arc->from], $arc->w);
	  }
	
	unset($ids_hash);
      }
  }


  /**
   * @return bool
   */
  function good_edge($from, $to)
  {
    if (($this->vertex[$from]->net_id != $this->vertex[$to]->net_id) ||
	($this->vertex[$from]->line_id != $this->vertex[$to]->line_id))
      return TRUE;

    // else: nodes are in the same network and line 
    foreach ($this->adjlist[$from] as $ei)
      if ($ei->to == $to)
	return FALSE;
      foreach ($this->adjlist[$to] as $ej)
	if (($ei->to == $ej->to)||($ej->to == $from))
	  return FALSE;
    return TRUE;
  }

  /**
   * 
   */
  function add_crossline_edges()
  {
    // eligible edges 
    $edges = $this->grid->find_closed_points(CLOSE_LIMIT_0);
    // filter the founded edges 
    while ($e = array_shift($edges))
      {
	list($from, $to) = $e;
	if ($this->good_edge($from, $to))
	  {
	    Util::log(basename(__FILE__) . '['.__LINE__.']',
		      $this->vertex[$from]->name.' -> '.$this->vertex[$to]->name);
	    $this->add_edge($from, $to, 2);
	    $this->add_edge($to, $from, 2);
	  }
      }
  }
  
  /**
   * 
   */
  function bf_buildroad($node, array $pre, array &$road)
  {
    if ($node == $pre[$node])
      array_push($road, $node);
    else
      {
	$this->bf_buildroad($pre[$node], $pre, $road);
	array_push($road, $node);
      }
  }

  /**
   * 
   */
  function bf_search($src, $dst)
  {
    $q = array();
    $pre = array();
    $visited = array_fill(0, count($this->vertex) - 1, FALSE);
    $dist = array_fill(0, count($this->vertex) - 1, 0);

    array_push($q, $src);
    $pre[$src] = $src;
    while (count($q) > 0)
      {
	$node = array_shift($q);
	if ($node == $dst)
	  break;
	$visited[$node] = TRUE;
	foreach ($this->adjlist[$node] as $e)
	  {
	    if ($visited[$e->to] ==  FALSE)
	      {
		$pre[$e->to] = $node;
		$dist[$e->to] = $dist[$node] + 1;
		array_push($q, $e->to);
	      }
	  }
      }

    unset($q);
    unset($visited);
    if ($node == $dst)
      {
	$road = array();
	$this->bf_buildroad($dst, $pre, $road);
	return $road;
      }
    return FALSE;
  }


  /**
   * @return int number of nodes 
   */
  function find_route(PT_MapPoint $src, PT_MapPoint $dst)
  {
    $walk_net = 0;
    $walk_line = 0;
    $src_name = 'Plecare';
    $dst_name = 'Sosire';

    $stations = array($src_name => $src,
		      $dst_name => $dst);
    $this->networks[$walk_net]->lines[$walk_line]->add_stations($stations);
    
    // pre-process network 
    $this->grid->arrange();
    $this->add_crossline_edges();
    // add source and destionation nodes 
    $src_id = $this->add_node($walk_net, $walk_line, $src_name);
    $dst_id = $this->add_node($walk_net, $walk_line, $dst_name);

    // map the points to the internal grid 
    $src_p = new PT_GridPoint($src_id, $src);
    $dst_p = new PT_GridPoint($dst_id, $dst);
   
    // * search source surrounding increasing the area size
    $area_size = CLOSE_LIMIT_0;
    do 
      {
	// check to see if the destination is directly reachable
	if (($src_p->dx($dst_p) < $area_size) &&
	    ($src_p->dy($dst_p) < $area_size))
	  {
	    // direct route 
	    return array($src_id, $dst_id);
	  }
	$src_links = $this->grid->find_nearby_points($src_p, $area_size);
	$area_size = $area_size + CLOSE_LIMIT_0;
      }
    while (count($src_links) == 0);
    // add edges to the links 
    foreach ($src_links as $link)
      $this->add_edge($src_id, $link, 2); 

    // * destionation
    $area_size = CLOSE_LIMIT_0;
    do 
      {
	$dst_links = $this->grid->find_nearby_points($dst_p, $area_size);
	$area_size = $area_size + CLOSE_LIMIT_0;
      }
    while (count($dst_links) == 0);
    // add edges to the links
    foreach ($dst_links as $link)
      $this->add_edge($link, $dst_id, 2);     

    Util::log(basename(__FILE__) . '['.__LINE__.']',
	      print_r($src_links, true));
    Util::log(basename(__FILE__) . '['.__LINE__.']',
	      print_r($dst_links, true));

    return $this->bf_search($src_id, $dst_id);
  }

  /**
   * @return int number of nodes 
   */
  function print_content()
  {
    $str = 'Nodes = '. $this->nodes_no() . "\n";
    foreach (range(0, count($this->vertex) - 1) as $node_id)
      {
	$str .= "$node_id -> ";
	if (count($this->adjlist[$node_id]) > 0)
	  {
	    foreach ($this->adjlist[$node_id] as $e)
	      $str .= $e->to . " ";
	  }
	$str .= "\n";
      }      
    Util::log(basename(__FILE__) . '['.__LINE__.']',
	      $str);
  }

  /**
   * 
   */
  function print_vertex()
  {
    $str = 'Vertex: ';
    foreach (range(0, count($this->vertex) - 1) as $node_id)
      {
	$str .= print_r($this->vertex[$node_id], true) . "\n";
      }
    Util::log(basename(__FILE__) . '['.__LINE__.']',
	      $str);
  }

  /**
   * @return int number of nodes 
   */
  function nodes_no()
  {
    return count($this->vertex) - 1;
  }

  /**
   * @return array set of PT_MapNode
   */
  function map_road($road)
  {
    $map_road = array(); 
    
    if (count($road) == 0)
      return FALSE;

    foreach ($road as $node)
      {
	$net_id = $this->vertex[$node]->net_id; 
	$line_id = $this->vertex[$node]->line_id; 
	$name = $this->vertex[$node]->name;
	array_push($map_road, 
		   new PT_MapNode($name,
				  $net_id,
				  $this->networks[$net_id]->lines[$line_id]->name,
				  $this->networks[$net_id]->lines[$line_id]->stations_hash[$name]
				  )
		   );
      }
    return $map_road;
  }
  
}

?>